A wide variety of memory devices can be used to maintain and store data and instructions for various computers and similar systems. In particular, flash memory is a type of electronic memory media that can be rewritten and that can retain content without consumption of power. Unlike dynamic random access memory (DRAM) devices and static random memory (SRAM) devices in which a single byte can be erased, flash memory devices are typically erased in fixed multi-bit blocks or sectors. Flash memory technology can include NOR flash memory and/or NAND flash memory, for example. NOR flash memory evolved from electrically erasable read only memory (EEPROM) chip technology, in which, unlike flash memory, a single byte can be erased; and NAND flash memory evolved from DRAM technology. Flash memory devices typically are less expensive and denser as compared to many other memory devices, meaning that flash memory devices can store more data per unit area.
Flash memory has become popular, at least in part, because it combines the advantages of the high density and low cost of EPROM with the electrical erasability of EEPROM. Flash memory is nonvolatile; it can be rewritten and can hold its content without power. It can be used in many portable electronic products, such as cell phones, portable computers, voice recorders, thumbnail drives and the like, as well as in many larger electronic systems, such as cars, planes, industrial control systems, etc. The fact that flash memory can be rewritten, as well as its retention of data without a power source, small size, and light weight, have all combined to make flash memory devices useful and popular means for transporting and maintaining data.
When flash memory is used to provide a reliable and efficient secondary memory subsystem two characteristics must be considered. One characteristic of flash memory is that it can only write data in one direction, in other words, a “1” can become a “0” but a “0” can not then become a “1”. The other characteristic of flash memory to be considered, often referred to as cycle endurance, is the number of times the addressable elements of the device can be erased and programmed before becoming unreliable. Both of these characteristics, which are related, adversely affect the reliability and the efficiency of the device.
In order to write data to a given location in a flash memory requiring a state opposite to that which the device supports requires the location be initialized. The initialization occurs as a result of the erase process; however, at some point in time, after numerous erase program cycles, a given location may either no longer be initialized to a known state or may no longer retain the data as written. As a result of having a finite number of times that a device can cycle between the erase (i.e., initialization) and program state before becoming unreliable, previous attempts to mitigate the problem have focused on extending storage persistence of the device by minimizing the number of erase program cycles.
In current flash memory devices the system writes to a particular address based on one-to-one relationship between the logical or system address and the physical address. If a particular address is used at a higher frequency than other addresses, which is characteristic of the one-to-one relationship, those locations will characteristically undergo more frequent erase program cycles. In addition to latency that is introduced by the write operation requiring initialization prior to recording, the flash memory device will eventually fail based on over use of addresses having a higher erase program frequency (i.e., cycle endurance) while other addresses experience minimal erase program cycling.
FIG. 1 provides a timeline representation 100 of the read and write operations in conventional flash memory device utilizing a one-to-one relationship between the logical/system address and the physical address, in accordance with the prior art. This type of addressing relationship is generally beneficial in that it is simple to implement and provides for minimal latency experienced in determining the location of the data's physical address (i.e., the read operation). For example at block 104, a read operation 102 ensues by providing a system address “1001”. At block 106, since the system address has a one-to-one relationship with the physical address, the physical address will be the same as the system address thus, as shown in this example, the physical address is also “1001”. This one-to-one relationship allows for the system to retrieve the data from data store 108 in the location 110 designated as physical address “1001” without introducing any latency in the read operation.
However, as illustrated in FIG. 1, the conventional write operation 112 in a flash memory device utilizing a one-to-one relationship between the logical/system address and the physical address introduces significant latency due to the flash memory requiring initialization (i.e., erase) of the media prior to recording information. At block 114, a write operation ensues by providing a system address “1001”. A read operation must precede the erase operation due to unit size difference of the erase operation versus the write operation. Thus at block 116, the system attempts to read all of the pages within the block indicated by physical address “1000” through “1002” into a volatile memory commonly referred to as a merge buffer. The reading of all pages within the block is indicated in data store 108 by location 118, which includes location 110 designated as physical address “1001”.
Once all of the pages within the block have been read, the erase operation, indicated by block 120, ensues. The erase operation, which typically requires about ten times the amount of time required for the actual write operation, will erase all of locations 122 in data store 108 associated with physical addresses “1000” through “1002”. Once the erase operation is complete, a merge operation, which combines the unchanged data from location 1000 and 1002 with the new data for location 1001, ensues to prevent the loss of data. As a result of the merge, the amount of data to be written is typically significantly larger that the size of the original write request. The merge operation is indicated by block 124 and results in the merged data from address “1001” merged into location 126 encompassing physical addresses “1000”-“1002” within data store 108. Once the data is merged, at block 128, the system writes out all of the pages back to the block, illustrated in the data store 108 as data residing in the “1001” location 110 and the “1000” and “1002” locations 118.
The write operation that occurs when a one-to-one relationship exists between the system address and the physical address exposes large amounts of data to possible loss in the event of loss of power during the write operation. This is because once the data is erased during the write operation it is no longer available and cannot be recovered. In addition, as previously mentioned, system addresses that are written at a high frequency will typically fail sooner due to cycle endurance limitations.
FIG. 2 provides an architectural overview of a system 200 utilizing flash memory having a one-to-one relationship between the system address and the physical address, according to the prior art. The host command interface 202 is operable to interpret commands for the device. If the command is a data command, the host command interface 202 sends the data to the Level 1 cache 204 in the volatile memory 206 through the host data interface 208 and the Level 1 data cache controller 210. The host command interface 202 is also in communication with flash management 212 and the host command interface 202 indicates to the flash management 212 the need to perform either a read operation from or a write operation to the data store 220. Based on the one-to-one address relationship, flash management 212 will receive the system address from the host command interface 202 and use the address as the physical address to read or write data.
If the command received from the host command interface 202 is a read command and the content is not located in the Level 1 cache, the flash management 212 will retrieve the data from the data pages 216 within the NAND memory 218 of the data store 220 via the data storage NAND media interface 222, store the retrieved data in the Level 1 cache 204 and inform the host command interface 202 of the data availability.
If the command received from the host command interface 202 is a write command, the flash management 212 will read all the data pages 216 in the block associated with the address into merge buffer 224, then erase the data from the location within the data pages 216 on the NAND memory 218 in the data store 220. Once erased the flash management will command a merge operation and the merged data is stored in the merge buffer 224 of volatile memory 226. Once the data is merged it is subsequently written to the location associated with the physical address in the data pages 216 of the NAND memory 218 of the data store 220.
The write operation that occurs when a one-to-one relationship exists between the system address and the physical address exposes large amounts of data to possible loss in the event of loss of power during the write operation. This is because once the data is erased during the write operation it is no longer available and cannot be recovered. In addition, as previously mentioned, system addresses that are written at a high frequency will typically fail sooner due to cycle endurance limitations.
Thus, a need exists to develop a method and system for reading and writing data to flash memory that mitigates wear on the physical device. The desired method and system should serve to distribute writes across the media, thus limiting the amount on times that data is written to a specific location in the nonvolatile flash memory. Thereby, lessening the likelihood of cycle endurance causing premature failure of the flash media. Additionally, and paramount to the present innovation, the desired system and method should provide for ability to recover data in instances in which a write operation is occurring and an error or failure occurs, such as a failure attributed to a power failure or like.
In addition, in order for the method and system for reading and writing data to flash memory to maintain its accuracy through events that disrupt the normal process of updating the data in non-volatile memory, such as a sudden loss of power, a system of logging the transactions must be established. This system will further provide for a process of recovering the transaction record and updating the non-volatile data after such a disruption, as would result upon subsequent power-up after a sudden loss of power event. In a conventional approach of logging, these transactions are recorded in the sequence with which they occur, that is, in a linear fashion. In such a system, when a recovery and update is required, the process is also linear and requires a high degree of processing capability to identify those transactions that belong to the same portion of the data structure, filter duplicates that vary over time and organize the information into update units of cache-lines. Thus, the overall recovery process in such an approach is potentially time-consuming and generally inefficient.
Thus, a need exists to develop a method and system for recording transactions in a manner that is efficient to both the recovery and update process should there be a disruption to the normal update process, such as a sudden power loss. The desired method and system should aggregate transactions in such a fashion that the amount of time and effort required to recover the modified data from such an event is minimized. In this regard, the desired methods and systems for recording the transactions should provide for a recovery search operation that is limited to identifying duplicate locations within the cache-line and keeping only the most recent modification. By providing such methods and systems that pre-organize the transactions the overall search process is greatly reduced and flexibility may be realized in implementing cache-line eviction processing in the event that the cache is determined to be full.